package com.剑指offer.第五章;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 设计一个新增、删除、获取元素的时间复杂度都为O(1)的容器
 * <p>
 * 获取元素 使用数据或list 可以达到0(1)
 * 新增元素o(1) 可以使用哈希表
 */
public class FastMap {

    private HashMap<Integer, Integer> map = new HashMap<>();

    private ArrayList<Integer> list = new ArrayList<>();


    public boolean insert(Integer val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size());
        return true;
    }


    /***
     * 删除一个元素 从数组中删除元素 是o(N) 因为需要向前移动
     *
     * 可以将这个删除的元素移动到最后，然后再删除
     * @param val
     * @return
     */
    public boolean remove(Integer val) {
        if (!map.containsKey(val)) {
            return false;
        }

        // 首先获取这个元素的位置
        Integer location = map.get(val);
        map.remove(val);
        // 将最后一个元素的替换
        map.put(list.get(list.size() - 1), location);
        list.add(location - 1, list.get(list.size() - 1));
        list.remove(list.size() - 1);
        return true;
    }

}
